package main

import (
	"fmt"
)

// 制作斐波那契数列
func makeFabArray(arr []int) []int {
	length := len(arr)

	flblen := 0
	first, secord, third := 1, 2, 3
	for third < length { //找出最接近的菲薄拿起
		third, first, secord = first+secord, secord, third //叠加计算菲薄纳妾
		flblen++
	}

	fmt.Println(third, first, secord)

	fb := make([]int, flblen)
	fb[0] = 1
	fb[1] = 1

	for i := 2; i < flblen; i++ {
		fb[i] = fb[i-1] + fb[i-2]

	}

	return fb
}

//查询数组
func fab_search(arr []int, val int) int {
	length := len(arr)
	fabArr := makeFabArray(arr) //定制匹配的斐波那契额数组

	filllength := fabArr[len(fabArr)-1] //填充长度

	fillArr := make([]int, filllength) //填充的数组
	for i, v := range arr {
		fillArr[i] = v
	}

	lastdata := arr[length-1] //填充最后一个大数
	for i := length; i < filllength; i++ {
		fillArr[i] = lastdata //填充数据
	}
	// fmt.Println(fillArr, length) //填充以后的数组

	left, mid, right := 0, 0, length //类似二分查找
	kindex := len(fabArr) - 1        //游标

	for left <= right {
		mid = left + fabArr[kindex-1] - 1 //菲薄纳妾切割
		if val < fillArr[mid] {
			right = mid - 1 //类似二分查找
			kindex--

		} else if val > fillArr[mid] {
			left = mid + 1
			kindex -= 2

		} else {
			if mid > right {
				return right //越界
			} else {
				return mid
			}
		}

	}

	return -1
}

func main() {
	arr := make([]int, 1000, 1000)
	for i := 0; i < 1000; i++ {
		arr[i] = i*2 + 5
	}

	// fmt.Println(arr)
	index := fab_search(arr, 205)

	fmt.Println("index", index)

	if index == -1 {
		fmt.Println("找不到")
	} else {
		fmt.Println("找到")
	}
}
